package com.duoduo.algs4.Fundamentals;

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;

import com.duoduo.algs4.util.RedirectStream;

import edu.princeton.cs.introcs.In;
import edu.princeton.cs.introcs.StdIn;
import edu.princeton.cs.introcs.StdOut;

public class BinarySearchRecursion {

	public static int rank(int key, int[] a) {
		//打印深度
		return rank(key, a, 0, a.length - 1, 0);
		//不打印深度
		// return rank(key, a, 0, a.length - 1);

	}

	public static int rank(int key, int[] a, int lo, int hi) {
		if (lo > hi) {
			return -1;
		}
		int mid = lo + (hi - lo) / 2;
		if (key == a[mid]) {
			return mid;
		} else if (key < a[mid]) {
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
		return rank(key, a, lo, hi);
	}

	// 打印递归深度 P35 1.1.22
	public static int rank(int key, int[] a, int lo, int hi, int deeps) {
		StdOut.println("此次递归的深度为:" + deeps + " lo:" + lo + " hi:" + hi);
		if (lo > hi) {
			return -1;
		}
		int mid = lo + (hi - lo) / 2;
		if (key == a[mid]) {
			return mid;
		} else if (key < a[mid]) {
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
		return rank(key, a, lo, hi, deeps + 1);
	}

	public static void testConsole(String whiteListName, String guestListName)
			throws IOException {
		int[] whiteList = In.readInts(whiteListName);
		FileInputStream fis = RedirectStream.redirectFileToStdin(guestListName);
		Arrays.sort(whiteList);
		while (!StdIn.isEmpty()) {
			int key = StdIn.readInt();
			if (rank(key, whiteList) == -1)
				StdOut.println(key);

		}
		if (fis != null) {
			fis.close();
		}

	}

	public static void main(String[] args) throws IOException {

		testConsole(args[0], args[1]);

	}
}